具有遲滯現象下一個提取預測器之訓練

专利摘要:
本發明係關於一種用於有效分支預測之系統及方法。一處理器包括兩個分支預測器。一第一分支預測器快速地產生分支預測資料，諸如一分支方向及一分支目標位址。第二分支預測器在一稍後時間且以更高預測準確度產生分支預測資料。控制邏輯可判定來自該第一分支預測器及該第二分支預測器中之每一者的分支預測資料是否匹配。若發生一失配，則可用由該第二分支預測器產生之該分支預測資料來訓練該第一預測器。一經儲存的遲滯現象指示可指示一給定分支指令展現關於其分支方向的一頻繁交替型樣。此行為可歸因於訓練不能夠跟上該改變分支方向而引起連貫的分支誤預測。在判定發生此條件時，控制邏輯可阻止對該第一預測器之訓練。
公开号:TW201324343A
申请号:TW101135374
申请日:2012-09-26
公开日:2013-06-16
发明作者:Andrew J Beaumont-Smith；Ramesh B Gunna
申请人:Apple Inc；
IPC主号:G06F1-00

专利说明:
具有遲滯現象下一個提取預測器之訓練
本發明係關於微處理器，且更特定言之，係關於分支預測機制。
在每一時脈循環期間，微處理器理想地針對管線之每一級產生指令之有用執行。然而，管線中之暫停可阻止在一或多個特定管線級期間執行有用工作。一些暫停可持續若干時脈循環且顯著地降低處理器效能。暫停之實例為誤預測之分支指令。
用於減小暫停之負面效應的技術包括使管線級重疊、允許指令之無次序執行及支援同時多執行緒。然而，若干時脈循環之暫停仍歸因於可阻止隱藏所有暫停循環的有次序淘汰(retirement)而降低處理器之效能。為了阻止此效能損失，可使用用於減少多循環暫停之發生的技術。此技術之一實例為分支預測。
分支預測技術預測分支指令之條件的評估。另外，分支預測技術可預測分支目標位址。分支預測邏輯可為複雜的以便提供高準確度。因此，分支預測邏輯可使用多個時脈循環來執行評估及計算以產生條件及分支目標位址之結果。然而，在此等多個時脈循環期間，自指令快取記憶體提取指令。若分支預測邏輯判定應提取其他指令，則可清空此等經提取指令。
分支預測邏輯可利用犧牲準確度以獲得更快結果之邏輯。然而，較低準確度可引起具有變化的分支型樣之小的重複的迴圈分支得不到恰當評估之情形。此狀況引起大多數時間下之誤預測及對應管線中之指令不斷地被清空。
鑒於上文，需要用於有效分支預測之有效方法及機制。
本發明係關於用於有效分支預測之系統及方法。在一實施例中，一處理器包括兩個分支預測器。一第一分支預測器可快速地產生分支預測資料，諸如一分支方向及一分支目標位址。在一些實施例中，該第一分支預測器在一單一循環內產生分支預測資料。該第二分支預測器可在一稍後時間且以更高預測準確度產生分支預測資料。控制邏輯可判定來自該第一分支預測器及該第二分支預測器中之每一者的分支預測資料是否匹配。
若該控制邏輯判定發生一失配，則該控制邏輯可訓練該第一預測器。訓練可包括用由該第二分支預測器產生之該分支預測資料來更新在該第一預測器中之經儲存值。然而，儘管有該經偵測失配，該控制邏輯仍可判定不執行訓練。該第一預測器或另一位置可儲存特定分支指令之遲滯現象之一指示。遲滯現象之一指示可指示一給定分支指令展現關於其分支方向的一頻繁交替型樣。此行為可歸因於該訓練不能夠跟上該改變分支方向而引起分支誤預測。在判定發生此條件時，該控制邏輯可阻止該第一預測器之訓練。
將在參考以下描述及圖式之後進一步瞭解此等及其他實施例。
雖然本發明易具有各種修改及替代形式，但在圖式中以舉例方式展示了其特定實施例，且將在本文中對其進行詳細描述。然而應理解，該等圖式及對其之詳細描述並非意欲將本發明限於所揭示的特定形式，而正相反，本發明將涵蓋屬於由附加申請專利範圍界定的本發明之精神及範疇內的所有修改、等效物及替代物。如遍及本申請案所使用，詞「可」以許可之意義(亦即，意謂有可能)而非強制性之意義(亦即，意謂必須)來使用。類似地，詞「包括」意謂包括但不限於。
各種單元、電路或其他組件可被描述為「經組態以」執行一或多項任務。在此等上下文中，「經組態以」為結構之寬泛陳述，其一般意謂「具有」在操作期間執行該或該等任務的「電路」。因而，甚至在單元/電路/組件當前未接通時，單元/電路/組件仍可經組態以執行任務。一般而言，形成對應於「經組態以」之結構之電路可包括硬體電路。類似地，為了描述之方便起見，各種單元/電路/組件可經描述為執行一或多項任務。此等描述應解釋為包括片語「經組態以」。陳述經組態以執行一或多項任務之單元/電路/組件明確地意欲不援引35 U.S.C.§ 112第六段對彼單元/電路/組件之解釋。
在以下描述中，闡述眾多特定細節以提供對本發明之透徹理解。然而，一般熟習此項技術者應認識到，可在無此等特定細節的情況下實踐本發明。在一些情況下，並未詳細展示熟知電路、結構及技術以避免使本發明模糊不清。
參看圖1，展示說明處理器100之前端的一實施例之一般化方塊圖。管線100可利用至少一個多級管線以用於處理指令。指令快取記憶體(i-cache)120可儲存軟體應用程式之指令。可自i-cache 120提取由程式計數器(PC)位址指示之一或多個指令，藉由位址選擇器110傳送程式計數器(PC)位址。若不存在指令快取記憶體未命中，則每一時脈循環可自指令快取記憶體120提取多個指令。
處理器100可實施允許一或多個虛擬位址空間對執行軟體可見之位址轉譯方案。可將在虛擬位址空間內之記憶體存取轉譯到對應於可用於處理器100的實際實體記憶體之實體位址空間。在處理器100的使用位址轉譯之實施例中，可使用實體位址位元而非虛擬位址位元來部分地或全部地定址指令快取記憶體120。舉例而言，指令快取記憶體120可將虛擬位址位元用於快取記憶體索引且將實體位址位元用於快取記憶體標籤。
為了避免在執行快取記憶體存取時執行全記憶體轉譯之成本，處理器100可將近來及/或頻繁地使用之虛擬至實體位址轉譯的集合儲存於轉譯後備緩衝器(TLB)中，出於說明之容易起見未展示轉譯後備緩衝器(TLB)。
增量器112可產生下一個循序PC位址。在一實施例中，下一個提取預測器130及分支預測器150中之每一者可在位址選擇器110中變更指令的提取。舉例而言，可將與無條件分支作業碼相關聯之絕對位址值發送至位址選擇器110。此位址值亦可被稱作分支目標位址或下一個提取程式計數器(PC)位址。下一個提取預測器130及分支預測器150中之每一者可將經預測分支目標位址發送至位址選擇器110。
下一個提取預測器130可基於針對給定分支預測之快速預測產生非循序PC位址。在一實施例中，下一個提取預測器130包括下一個提取表132及下一個提取控制邏輯134。在一實施例中，下一個提取控制邏輯134以雜湊函數將用以自指令快取記憶體120提取指令之PC位址的至少一部分與自身的另一部分組合或與其他值組合。此特定雜湊函數可為相對快速互斥或(XOR)組合函數。此雜湊函數之輸出可用以索引下一個提取表132。在下一個提取表132中之命中可提供用於自指令快取記憶體120提取指令的下一個PC位址。在一實施例中，下一個提取預測器為單一循環預測器。
分支預測器150亦可接收用以自指令快取記憶體120提取指令之PC位址中之至少一部分。分支預測器150亦可以單獨的雜湊函數將所接收PC位址之至少一部分與自身的另一部分組合或與諸如歷史資訊之其他值組合。可執行各種雜湊函數以判定至一或多個型樣歷史表(PHT)、分支目標緩衝器(BTB)及/或用以提供分支預測資料之其他表的索引。分支預測資料可包括分支方向及分支目標位址。分支預測器150可利用多個時脈信號來既判定分支指令之條件的結果且又判定分支目標位址。
分支預測器150可以高於下一個提取預測器130之預測準確度提供分支預測資料。然而，分支預測器150利用多個循環產生更準確的分支預測資料。因此，下一個提取預測器130可用以提供快速、初始分支預測。隨後，分支預測器150可在稍後時間驗證該初始分支預測。
由下一個提取預測器130產生之預測資料可沿著處理器100之管線經儲存且經分級。可比較經分級預測資料與在稍後管道級處由分支預測器150產生之預測資料。當下一個提取預測器130產生不匹配在稍後時間由分支預測器150產生之預測資料的分支預測資料時，可用由分支預測器150產生之預測資料來更新或訓練下一個提取預測器130。如本文中所使用，訓練下一個提取預測器130可包括用由分支預測器150產生之分支預測資料來寫入或更新在下一個提取預測器130中的經儲存參數。具有頻繁交替型樣之分支指令可引起大量分支誤預測。大量分支誤預測可由分支預測器150對下一個提取預測器130的訓練不能夠跟上頻繁交替型樣造成。
在一實施例中，下一個提取表132可儲存關於對應分支指令是否已展現出遲滯現象之指示。遲滯現象可指示對應分支指令之分支方向具有頻繁交替型樣。舉例而言，對應分支指令可在採納與不採納之間頻繁地交替。在一些實施例中，下一個提取表132之每一項可儲存一遲滯現象位元。在一實例中，設定的遲滯現象位元可指示對應分支指令可展現出頻繁交替型樣。重設的遲滯現象位元可指示對應分支指令可不展現出頻繁交替型樣。
當在由下一個提取預測器130產生的分支預測資料與由分支預測器150對於相同分支指令產生的分支預測資料之間找到失配時，控制邏輯可判定是否訓練下一個提取預測器130。此控制邏輯可利用分支指令之遲滯現象之對應指示。遲滯現象之指示可阻止對下一個提取預測器130之後續訓練。馬上提供利用遲滯現象之指示來改良分支預測的方法及機制之進一步描述。首先，提供管線100之進一步描述。
解碼單元140可解碼多個經提取指令之作業碼。或者，指令可經劃分成微指令或微作業碼。如本文中所使用，術語「指令」及「微作業碼」為可互換的，因為本發明可與利用任一實施之架構一起使用。解碼單元140可將具有額外經解碼資訊之指令發送至處理器100中之其他組件以用於在稍後管道級中的指令處理。舉例而言，解碼單元140可分配分派佇列中的項。暫存器重新命名、指令排程、執行算術運算及/或執行記憶體存取及有次序淘汰為稍後指令處理步驟之一些實例。指令處理單元160通常可執行此等步驟中之一者。
現轉而參看圖2，展示下一個提取預測器200之一實施例的一般化方塊圖。如圖所示，下一個提取預測器200接收當前提取PC 202。所接收當前提取PC 202可包括識別當前分支指令之用以自指令快取記憶體120提取指令的位址之足夠數目個位元。當前提取PC 202可來自位址選擇器110。一或多個方法可用以在用當前提取PC 202提取之多個指令內的兩個或兩個以上分支指令之間避免混淆及進行歧義消除。
在一實施例中，可藉由雜湊函數220對所接收當前提取PC 202之位元與其自身執行雜湊。在一實例中，可藉由雜湊函數220內之互斥或(XOR)組合函數將當前提取PC 202之偏移部分與當前提取PC 202之上部位元組合。在其他實例中，可將偏移部分與除當前提取PC 202之上部位元中的每一者之外的位元組合。另外，可使用非連續位元及其他組合邏輯。可使用其他值(未圖示)，諸如歷史資訊、計數值等等。眾多此等替代物為可能的且預期的。然而，在各種實施例中，可預期在單一時脈循環之後由下一個提取預測器200產生分支預測資料。因此，雜湊函數220之功能性可係針對快速及有效雜湊計算。
下一個提取預測器200可包括下一個提取表240。下一個提取表240可至少藉由雜湊函數220之輸出來索引。下一個提取表240可儲存對應於分支指令之資訊且用以產生分支預測資料。分支預測資料可包括分支方向及分支目標位址；諸如經預測的下一個提取PC位址。下一個提取表240可儲存條件及無條件分支指令之資訊。另外，下一個提取表240可儲存直接及間接分支指令之資訊。
條件分支指令執行在指令串流中採納哪一路徑之判定。若分支指令判定未滿足條件，則分支指令被認為不被採納，且執行程式次序中之下一個循序指令。然而，若分支指令判定滿足條件，則分支指令被認為被採納。對於被採納的分支指令，執行並非程式次序中之下一個循序指令而是位於經計算分支目標位址處的指令。無條件分支指令被當作總是採納的條件分支指令。不存在要測試之條件，且以不同於循序次序之序列執行指令。
對於直接分支指令，分支目標位址可由相對於程式計數器(PC)值的偏移規定，偏移可儲存於分支指令自身中。對於間接分支指令，分支目標位址可由暫存器或記憶體中之值規定，其中可在分支指令中識別暫存器或記憶體位置。另外，可將不同值載入規定分支目標位址之暫存器或記憶體位置。
在一實施例中，下一個提取表240具有多個項242a至242g。項242a至242g中之每一者可包括若干欄位，諸如至少欄位250至256。在一實施例中，欄位250儲存狀態資訊，諸如至少有效位元。欄位252儲存雜湊輸出識別符(ID)。此識別符值可為在較早時間由雜湊函數220產生之值。在一實施例中，欄位252可儲存經雜湊之提取PC位址的額外位元。在其他實施例中，雜湊輸出ID足以用於提供在下一個提取表240中之快速及相異查找。
表240中之欄位254可儲存對應分支指令之經預測下一個提取PC位址值。欄位256可儲存指示對應分支指令是否表明具有遲滯現象之分支行為的指示。舉例而言，對應分支指令之分支方向可具有頻繁交替型樣。在極端狀況下，對應分支指令可在分支指令之每一執行期間在採納(T)方向與不採納方向(NT)之間交替。型樣可看起來像T、NT、T、NT等等。此型樣可難以在訓練下一個提取預測器200的同時偵測到。可在對應分支指令之每一次發生之後重新訓練下一個提取預測器200，但重新訓練可引起下一個提取預測器200再次誤預測分支指令。因此，儲存於欄位256中之遲滯現象的指示可用以停止針對對應分支指令之至少一次發生的重新訓練。在一實施例中，欄位256儲存單一位元以指示遲滯現象。
可至少將雜湊函數220之輸出用以索引下一個提取表240。可執行雜湊函數220之輸出與儲存於項242a至242g之欄位252中的雜湊輸出ID之比較。若找到匹配，則可自下一個提取表240讀取儲存於欄位254及256中之對應的下一個提取PC及遲滯現象的指示。可將命中狀態及可用以識別對應分支指令之雜湊輸出ID與儲存於欄位254及256中之資料組成一組。所有此資料可經分級且發送至稍後管道級以便由分支預測器150中之控制邏輯使用。分支預測器150可驗證所接收資料是否與其在稍後時間產生之分支預測資料一致。除了將資料發送至分支預測器150之外，可將自下一個提取表240讀取之下一個提取PC發送至位址選擇器110。
下一個提取預測器200亦可自分支預測器150接收資訊。可在分支預測器150驗證來自下一個提取預測器200的分支預測資料是否匹配由分支預測器150產生的分支預測資料之後接收此資訊。下一個提取預測器200可接收訓練控制信號204、雜湊輸出ID 206、下一個提取PC位址208及針對給定分支指令的遲滯現象之指示210。可將自分支預測器接收之此資料發送至更新邏輯230。更新邏輯可判定何時將資料寫入至下一個提取表240及要修改項242a至242g中之哪一項。
訓練控制信號204可為來自分支預測器150之用以修改下一個提取表240中的特定項之指示。雜湊輸出ID 206可用以索引下一個提取表240且識別項242a至242g中之給定項。下一個提取PC 208可用以覆寫儲存於經識別項之欄位254中的PC值。類似地，遲滯現象之所接收指示210可用以覆寫儲存於經識別項之欄位256中的指示。
訓練控制信號204或發送至下一個提取預測器200之其他指示符可識別在經識別項中覆寫哪些欄位。在一些狀況下，可更新下一個提取PC及遲滯現象之指示兩者。在其他狀況下，更新此兩個值中之一者，而不修改兩個值中之另一者。在一些狀況下，判定由下一個提取預測器200及分支預測器150產生之分支預測資料之間的失配，但不發生對下一個提取預測器200之訓練。對於此等狀況，訓練信號204指示在對應分支指令之下一個提取表240中將不執行修改。
現參看圖3，展示用於有效的下一個提取預測之方法300之一實施例的一般化流程圖。出於論述之目的，按循序次序展示稍後描述之方法的此實施例及後續實施例中之步驟。然而，在其他實施例中，一些步驟可按不同於所展示之次序發生，一些步驟可同時地執行，一些步驟可與其他步驟組合，且一些步驟可不存在。
在區塊302中，發送給定程式計數器(PC)以提取指令。在區塊304中，使用雜湊函數將給定PC之一或多個位元與其他控制值組合。其他控制值可為如較早描述之給定PC內的其他位元。在區塊306中，用至少雜湊函數之輸出索引下一個提取表。若在下一個提取表中發生未命中(條件區塊308)，則在區塊310中，可發送指示以使用下一個循序PC來提取指令。可將該指示自下一個提取預測器發送至位址選擇器。
若在下一個提取表中發生命中(條件區塊308)，則在區塊312中，可發送儲存於對應於該命中的項中之下一個提取PC以用於提取指令。可將下一個提取PC發送至位址選擇器。在區塊314中，可將分支預測資料發送至諸如分支預測器150之第二分支預測器以用於驗證分支預測資料。分支預測資料可包括至少下一個提取PC、遲滯現象之指示及命中/未命中狀態。命中/未命中狀態可指示經預測的採納/不採納分支方向。
現轉而參看圖4，展示說明用於下一個提取預測器之訓練更新邏輯400的一實施例之一般化方塊圖。在一實施例中，利用訓練更新邏輯400以回應於判定來自下一個提取預測器及用以驗證下一個提取預測器之分支預測器中之每一者的分支預測資料之間的失配而產生輸出。舉例而言，由此等兩個預測器中之每一者產生的下一個提取PC位址可不相同。通常，將接著進行下一個提取預測器之訓練。然而，為了阻止歸因於對應分支指令之頻繁交替型樣(諸如，分支指令之方向)的連貫誤預測，訓練更新邏輯400可判定是否可跳過訓練。在一些實施例中，失配鑑定可啟用在訓練更新邏輯400內最前面的邏輯以便在未發生失配時節省能量消耗。在其他實施例中，可關於訓練更新邏輯400之結果使用失配鑑定以判定是否將使用結果。
在一實施例中，更新邏輯420自更準確的分支預測器接收經預測分支方向(諸如，採納狀態信號410)。另外，更新邏輯420可自快速分支預測器接收經預測分支方向及遲滯現象之指示。在一實施例中，快速分支預測器可為具有下一個提取表之單循環下一個提取預測器。經預測分支方向可由表命中狀態指示。遲滯現象之指示可(例如)為儲存於下一個提取表之每一項中的單一位元。因此，更新邏輯420自下一個提取預測器接收命中狀態412及單一遲滯現象位元414。快速分支預測器及所得分支預測資料之其他實施例為可能的且預期的。
為了判定是否可發生訓練，可以若干不同方式實施更新邏輯420內之控制邏輯及演算法。一些實施實例可包括組合邏輯閘、狀態圖、場可程式化閘陣列(FPGA)及以諸如硬體描述語言或高階C程式設計語言之程式設計語言編寫的程式碼。程式碼可儲存於諸如硬碟、主機板上之電腦系統記憶體、軟碟或其他攜帶型記憶體儲存器等等的非暫時性儲存媒體上。程式碼之指令可載入至處理器中且在處理器內之硬體上執行以執行由程式碼描述的演算法。在一實施例中，更新邏輯420可使用自兩個分支預測器接收之值來判定由諸如下一個提取預測器的快速分支預測器使用之下一個提取PC位址是否將被由更準確的分支預測器產生之一下一個提取PC位址覆寫。
更新邏輯420中之列442說明基於列440及欄424至430中所展示之條件是否經評估為真的針對下一個提取PC位址之特定更新情形。在一實例中，如列440及欄428中所展示，若下一個提取預測器提供重設遲滯現象位元(非遲滯現象)，其中經重設的位元可指示針對對應分支指令未偵測到遲滯現象，且驗證分支預測器產生採納分支方向，則發生訓練。訓練可包括用由驗證分支預測器產生之下一個提取PC位址來覆寫儲存於下一個提取預測器中之對應分支指令的下一個提取PC位址。再次參看圖2，可將信號204至210自驗證分支預測器發送至下一個提取預測器200。信號204至210中之資訊可用以識別項242a至242g中之特定項，且至少覆寫儲存下一個提取PC位址之欄位254。
繼續圖4中之更新邏輯420的列440及欄428中所展示之經評估條件，可設定儲存於下一個提取預測器中之對應分支指令的遲滯現象位元。設定遲滯現象位元可另外覆寫儲存於下一個提取預測器中之下一個提取PC位址。再次參看圖2，信號204至210中之資訊可用以識別如較早所描述的項242a至242g中之特定項且至少覆寫儲存對應分支指令之遲滯現象的指示之欄位256。回到圖4，更新邏輯420中之列444說明基於欄424至430中所展示之條件是否經評估為真的針對對應分支指令之遲滯現象的指示之特定更新情形。
再次，可用下一個提取預測器與進行驗證的更準確的分支預測器之間的分支預測資料之失配來鑑定列440及欄424至430中之每一者中所展示的條件。此鑑定可在利用更新邏輯420中之演算法之前發生。或者，此鑑定可在藉由更新邏輯420中之演算法找到結果之後發生。在另一實例中，如列440及欄430中所展示，若下一個提取預測器在下一個提取表內提供經重設遲滯現象位元，其中重設位元可指示針對對應分支指令未偵測到遲滯現象，及命中狀態，則發生訓練。在此狀況下，訓練可包括使儲存於下一個提取預測器中之對應分支指令的下一個提取PC位址失效。使此特定下一個提取PC位址失效可藉由使下一個提取表240中之項242a至242g中的對應項失效來實現。另外，可在此經識別項中設定對應遲滯現象位元。
對於由更新邏輯420中之列440及欄424及426識別之狀況中的每一者，可跳過訓練。在此等狀況下，儘管偵測到下一個提取預測器與進行驗證的更準確的分支預測器之間的分支預測資料之失配，仍可跳過訓練。對於分支方向展現出頻繁交替型樣之特定分支指令而言，跳過訓練可增加分支預測準確度。在一實例中，指令快取記憶體120每一時脈循環提供4個經提取指令，且進行驗證的更準確的分支預測器利用5個時脈循環來產生分支預測資料。到了偵測到在下一個提取預測器與更準確的分支預測器之間的失配時，20個指令有資格被清空。消耗能量以處理此20個指令且工作之結果未被使用。因此，判定針對某些條件可跳過訓練可減少能量消耗且使管線充滿有用工作。
列440及欄424說明下一個提取預測器提供經設定遲滯現象位元之狀況，其中經設定位元可指示偵測到對應分支指令之遲滯現象。在欄424中所展示之狀況下，下一個提取預測器在下一個提取表內提供命中狀態，抑或進行驗證的更準確的分支預測器提供經預測採納分支方向。對於此狀況，列442展示可維持儲存於下一個提取預測器中之下一個提取PC位址。對於下一個提取預測器中之對應分支指令，未發生修改或訓練。對於此狀況，列444展示可重設對應遲滯現象位元，其中重設值可指示未偵測到對應分支指令之遲滯現象。
列440及欄426說明下一個提取預測器提供經設定遲滯現象位元之狀況，其中經設定位元可指示偵測到對應分支指令之遲滯現象。在欄426中所展示之狀況下，下一個提取預測器在下一個提取表內提供未命中狀態。另外，進行驗證的更準確的分支預測器提供經預測的不採納分支方向。對於此狀況，列442展示可維持儲存於下一個提取預測器中之下一個提取PC位址。對於下一個提取預測器中之對應分支指令，未發生修改或訓練。對於此狀況，列444展示亦可維持對應遲滯現象位元。
現參看圖5，展示用於有效分支預測訓練之方法500之一實施例的一般化流程圖。出於論述之目的，按循序次序展示稍後描述之方法的此實施例及後續實施例中之步驟。然而，在其他實施例中，一些步驟可按不同於所展示之次序發生，一些步驟可同時地執行，一些步驟可與其他步驟組合，且一些步驟可不存在。
在區塊502中，對於給定分支指令，由第一分支預測器產生第一預測資料。在區塊504中，對於相同給定分支指令，在稍後時間由第二預測器以高於第一預測器之準確度產生第二預測資料。在區塊506中，比較第一及第二預測資料。若判定在第一分支預測資料與第二分支預測資料之間未發生失配(條件區塊508)，則在區塊510中，可產生指示將不針對第一預測器執行訓練之指示。兩個分支預測器對於給定分支指令產生相同結果。
若判定在第一分支預測資料與第二分支預測資料之間發生失配(條件區塊508)，則在區塊512中，基於對應於給定分支指令之第一及第二預測資料以及遲滯現象的指示進行關於是否存在用於訓練第一預測器之條件的判定。再次簡短地參看圖4，此等條件可由更新邏輯420中之列440及欄424至430規定。若判定存在用於訓練第一預測器之至少一條件(條件區塊514)，則在區塊516中，可基於經判定條件針對給定分支指令更新第一預測器中之經預測方向、分支目標位址及遲滯現象之指示中的一或多者。可將由更準確的第二分支預測器產生之分支預測資料用以更新儲存於第一預測器中之值。
若判定不存在用於訓練第一預測器之條件(條件區塊514)，則方法500之控制流程移動至區塊510，且可產生用以指示將不針對第一預測器執行訓練之指示。在各種實施例中，至少偵測到給定分支指令之分支方向展現出頻繁交替型樣可阻止對第一預測器之訓練。再次參看圖4，更新邏輯420可說明利用遲滯現象來判定用於阻止對第一預測器之訓練的條件之一實施例。
儘管已相當詳細地描述了上文實施例，但一旦完全瞭解以上揭示內容，則眾多變化及修改將對熟習此項技術者變得顯而易見。希望將以下申請專利範圍解釋為涵蓋所有此等變化及修改。
100‧‧‧處理器/管線
110‧‧‧位址選擇器
112‧‧‧增量器
120‧‧‧指令快取記憶體(i-cache)
130‧‧‧下一個提取預測器
132‧‧‧下一個提取表
134‧‧‧下一個提取控制邏輯
140‧‧‧解碼單元
150‧‧‧分支預測器
160‧‧‧指令處理單元
200‧‧‧下一個提取預測器
202‧‧‧當前提取PC
204‧‧‧訓練控制信號
206‧‧‧雜湊輸出ID/信號
208‧‧‧下一個提取PC位址/信號
210‧‧‧遲滯現象之指示/信號
220‧‧‧雜湊函數
230‧‧‧更新邏輯
240‧‧‧下一個提取表
242a‧‧‧項
242b‧‧‧項
242g‧‧‧項
250‧‧‧欄位
252‧‧‧欄位
254‧‧‧欄位
256‧‧‧欄位
300‧‧‧用於有效的下一個提取預測之方法
400‧‧‧訓練更新邏輯
410‧‧‧採納狀態信號
412‧‧‧命中狀態
414‧‧‧單一遲滯現象位元
420‧‧‧更新邏輯
422‧‧‧欄
424‧‧‧欄
426‧‧‧欄
428‧‧‧欄
430‧‧‧欄
440‧‧‧列
442‧‧‧列
444‧‧‧列
500‧‧‧用於有效分支預測訓練之方法
圖1為處理器之前端的一實施例之一般化方塊圖。
圖2為下一個提取預測器之一實施例的一般化方塊圖。
圖3為說明用於進行有效的下一個提取預測之方法之一實施例的一般化流程圖。
圖4為說明用於下一個提取預測器之訓練更新邏輯400的一實施例之一般化方塊圖。
圖5為說明用於進行有效分支預測訓練之方法之一實施例的一般化流程圖。
200‧‧‧下一個提取預測器
202‧‧‧當前提取PC
204‧‧‧訓練控制信號
206‧‧‧雜湊輸出ID/信號
208‧‧‧下一個提取PC位址/信號
210‧‧‧遲滯現象之指示/信號
220‧‧‧雜湊函數
230‧‧‧更新邏輯
240‧‧‧下一個提取表
242a‧‧‧項
242b‧‧‧項
242g‧‧‧項
250‧‧‧欄位
252‧‧‧欄位
254‧‧‧欄位
256‧‧‧欄位

权利要求:
Claims (20)
[1] 一種處理器，其包含：一第一分支預測器，其經組態以：提供一給定分支指令是否具有遲滯現象之一指示；及針對該給定分支指令產生第一分支預測資料；一第二分支預測器，其經組態以針對該給定分支指令產生第二分支預測資料；及控制邏輯，其經組態以：回應於判定在該第一預測資料與該第二預測資料之間存在一失配，至少部分基於該第一預測資料及該第二預測資料中之至少一者及遲滯現象的該指示產生一輸出；其中該輸出用以判定是否訓練該第一分支預測器。
[2] 如請求項1之處理器，其中該遲滯現象指示該給定分支指令之分支方向具有一頻繁交替型樣。
[3] 如請求項2之處理器，其中該輸出係藉由利用該遲滯現象、該第一預測資料及該第二預測資料之一組合函數產生。
[4] 如請求項3之處理器，其中該輸出指示該給定分支指令具有遲滯現象，且該第一分支預測資料及該第二分支預測資料中之至少一者指示採納該給定分支指令。
[5] 如請求項3之處理器，其中該輸出指示該給定分支指令具有遲滯現象，且該第一分支預測資料及該第二分支預測資料中之每一者指示不採納該給定分支指令。
[6] 如請求項4之處理器，其中該第一分支預測器包含具有複數個項之一表，其中每一項經組態以儲存一下一個提取程式計數器(PC)位址及一遲滯現象指示。
[7] 如請求項4之處理器，其中該第二分支預測器具有高於該第一分支預測器之一分支預測準確度。
[8] 如請求項4之處理器，其中該第二分支預測器在比該第一分支預測器產生該第一分支預測資料所在的管道級遲的一管道級中產生該第二分支預測資料。
[9] 一種方法，其包含：提供來自一第一分支預測器之指示一給定分支指令是否具有遲滯現象的一指示；藉由該第一分支預測器針對該給定分支指令產生第一分支預測資料；藉由一第二分支預測器針對該給定分支指令產生第二分支預測資料；判定在該第一預測資料與該第二預測資料之間是否存在一失配；及至少部分基於該遲滯現象及該第一預測資料及該第二預測資料中之至少一者產生一輸出，其中該輸出用以判定是否訓練該第一分支預測器。
[10] 如請求項9之方法，其中該遲滯現象指示該給定分支指令之分支方向具有一頻繁交替型樣。
[11] 如請求項10之方法，其中產生該輸出包含基於該遲滯現象、該第一預測資料及該第二預測資料判定一組合輸出。
[12] 如請求項11之方法，其中該輸出指示該給定分支指令具有遲滯現象，且該第一分支預測資料及該第二分支預測資料中之至少一者指示採納該給定分支指令。
[13] 如請求項11之方法，其中該輸出指示該給定分支指令具有遲滯現象，且該第一分支預測資料及該第二分支預測資料中之每一者指示不採納該給定分支指令。
[14] 如請求項12之方法，其進一步包含更新該第一分支預測器以指示儘管未訓練該第一分支預測器，該給定分支指令不具有遲滯現象。
[15] 如請求項11之方法，其進一步包含回應於判定該輸出指示該給定分支指令不具有遲滯現象且該第二分支預測資料指示採納該給定分支指令，訓練該第一分支預測器且設定該指示以指示該給定分支指令具有遲滯現象。
[16] 如請求項11之方法，其進一步包含回應於判定該輸出指示該給定分支指令不具有遲滯現象且該第一分支預測資料指示採納該給定分支指令，訓練該第一分支預測器且設定該指示以指示該給定分支指令具有遲滯現象。
[17] 一種電腦可讀儲存媒體，其包含可操作以執行分支預測之程式指令，其中該等程式指令可經執行以：提供來自一第一分支預測器之指示一給定分支指令是否具有遲滯現象的一指示；藉由該第一分支預測器針對該給定分支指令產生第一分支預測資料；藉由一第二分支預測器針對該給定分支指令產生第二分支預測資料；判定在該第一預測資料與該第二預測資料之間是否存在一失配；及至少部分基於該遲滯現象及該第一預測資料及該第二預測資料中之至少一者產生一輸出，其中該輸出用以判定是否訓練該第一分支預測器。
[18] 如請求項17之儲存媒體，其中該遲滯現象指示該給定分支指令之分支方向具有一頻繁交替型樣。
[19] 如請求項18之儲存媒體，其中該等程式指令可進一步經執行以判定儘管該第一預測資料與該第二預測資料之間存在該失配，該輸出仍指示不對該第一分支預測器進行訓練。
[20] 如請求項19之儲存媒體，其中該輸出指示該給定分支指令具有遲滯現象且(1)該第一分支預測資料及該第二分支預測資料中之至少一者指示採納該給定分支指令，抑或(2)該第一分支預測資料及該第二分支預測資料中之每一者指示不採納該給定分支指令。

类似技术:

---

公开号 | 公开日 | 专利标题

---

TWI499975B|2015-09-11|具有遲滯現象下一個提取預測器之訓練

---

EP1851620B1|2010-09-29|Suppressing update of a branch history register by loop-ending branches

---

KR101459536B1|2014-11-07|사전 통지 기법들을 사용하여 프로그램의 순차적 흐름을 변경하기 위한 방법들 및 장치

---

US8935517B2|2015-01-13|System and method for selectively managing a branch target address cache of a multiple-stage predictor

---

US7143273B2|2006-11-28|Method and apparatus for dynamic branch prediction utilizing multiple stew algorithms for indexing a global history

---

US20150331691A1|2015-11-19|Branch prediction using multiple versions of history data

---

KR20070118135A|2007-12-13|인덱스당 2개 이상의 분기 타겟 어드레스를 저장하는 분기타겟 어드레스 캐시

---

JP2011100466A5|2013-07-04|

---

JP2008532142A5|2013-01-24|

---

TW201423584A|2014-06-16|提取寬度預測器

---

TWI428826B|2014-03-01|更新微處理器中之分支目標位址快取之方法以及相關之微處理器

---

JP2009536770A|2009-10-15|ブロックに基づく分岐先アドレスキャッシュ

---

US10664280B2|2020-05-26|Fetch ahead branch target buffer

---

KR20090089358A|2009-08-21|워킹 글로벌 히스토리 레지스터를 이용하기 위한 시스템 및 방법

---

US7836288B2|2010-11-16|Branch prediction mechanism including a branch prediction memory and a branch prediction cache

---

JP2020119504A|2020-08-06|分岐予測器

---

US20060112262A1|2006-05-25|Branch prediction of unconditionally executed branch instructions

同族专利:

---

公开号 | 公开日

---

KR101376900B1|2014-03-20|

---

JP2013120597A|2013-06-17|

---

CN103150142A|2013-06-12|

---

US8959320B2|2015-02-17|

---

EP2602711B1|2014-12-24|

---

CN103150142B|2015-10-21|

---

US20130151823A1|2013-06-13|

---

TWI499975B|2015-09-11|

---

EP2602711A1|2013-06-12|

---

WO2013085599A1|2013-06-13|

---

KR20130064002A|2013-06-17|

---

JP5927616B2|2016-06-01|

引用文献:

---

公开号 | 申请日 | 公开日 | 申请人 | 专利标题

---

US9012A||1852-06-15||Improved valve or gate for oblique-float paddle-wheels |

---

US4022A||1845-05-01||Improvement in machines for hackling and cleaning hemp and flax |

---

US7023A||1850-01-15||peters |

---

US5758142A|1994-05-31|1998-05-26|Digital Equipment Corporation|Trainable apparatus for predicting instruction outcomes in pipelined processors|

---

JP3494484B2|1994-10-12|2004-02-09|株式会社ルネサステクノロジ|命令処理装置|

---

JP3760041B2|1996-12-09|2006-03-29|松下電器産業株式会社|分岐予測する情報処理装置|

---

US6374349B2|1998-03-19|2002-04-16|Mcfarling Scott|Branch predictor with serially connected predictor stages for improving branch prediction accuracy|

---

US6553488B2|1998-09-08|2003-04-22|Intel Corporation|Method and apparatus for branch prediction using first and second level branch prediction tables|

---

US6115810A|1998-09-16|2000-09-05|Sun Microsystems, Inc.|Bi-level branch target prediction scheme with mux select prediction|

---

US6647490B2|1999-10-14|2003-11-11|Advanced Micro Devices, Inc.|Training line predictor for branch targets|

---

US6721877B1|2000-05-25|2004-04-13|Advanced Micro Devices, Inc.|Branch predictor that selects between predictions based on stored prediction selector and branch predictor index generation|

---

US20040225870A1|2003-05-07|2004-11-11|Srinivasan Srikanth T.|Method and apparatus for reducing wrong path execution in a speculative multi-threaded processor|

---

US20060036837A1|2004-08-13|2006-02-16|Stark Jared W|Prophet/critic hybrid predictor|

---

US20060190710A1|2005-02-24|2006-08-24|Bohuslav Rychlik|Suppressing update of a branch history register by loop-ending branches|

---

US7434037B2|2006-04-07|2008-10-07|International Business Machines Corporation|System for target branch prediction using correlation of local target histories including update inhibition for inefficient entries|

---

US7523298B2|2006-05-04|2009-04-21|International Business Machines Corporation|Polymorphic branch predictor and method with selectable mode of prediction|

---

US7707398B2|2007-11-13|2010-04-27|Applied Micro Circuits Corporation|System and method for speculative global history prediction updating|

---

CN101763248A|2008-12-25|2010-06-30|世意法（北京）半导体研发有限责任公司|用于多模式分支预测器的系统和方法|

---

CN104636274B|2010-03-29|2018-01-26|威盛电子股份有限公司|数据预取方法以及微处理器|US9811340B2|2012-06-18|2017-11-07|Intel Corporation|Method and apparatus for reconstructing real program order of instructions in multi-strand out-of-order processor|

---

CN104423929B|2013-08-21|2017-07-14|华为技术有限公司|一种分支预测方法及相关装置|

---

US9582285B2|2014-03-24|2017-02-28|Qualcomm Incorporated|Speculative history forwarding in overriding branch predictors, and related circuits, methods, and computer-readable media|

---

US9639368B2|2014-06-13|2017-05-02|International Business Machines Corporation|Branch prediction based on correlating events|

---

KR101624636B1|2015-03-03|2016-05-27|주식회사 에이디칩스|명령어 패치 장치 및 방법|

---

CN105867880B|2016-04-01|2018-12-04|中国科学院计算技术研究所|一种面向间接跳转分支预测的分支目标缓冲器及设计方法|

---

CN106406814B|2016-09-30|2019-06-14|上海兆芯集成电路有限公司|处理器和将架构指令转译成微指令的方法|

---

US10747539B1|2016-11-14|2020-08-18|Apple Inc.|Scan-on-fill next fetch target prediction|

---

US10613867B1|2017-07-19|2020-04-07|Apple Inc.|Suppressing pipeline redirection indications|

---

US10929136B2|2018-04-11|2021-02-23|Futurewei Technologies, Inc.|Accurate early branch prediction using multiple predictors having different accuracy and latency in high-performance microprocessors|

法律状态:

优先权:

---

申请号 | 申请日 | 专利标题

---

US13/313,691|US8959320B2|2011-12-07|2011-12-07|Preventing update training of first predictor with mismatching second predictor for branch instructions with alternating pattern hysteresis|

---